Fig.2 Lack of synchronization in the body of rc 4_ safe _ select leads to an unpredictable result.

The consequences are obvious:

• Both streams will work with the same RC 4 instance . And the stream that reached rc 4_ safe last will expect a “race favorite” in the critical section.
• Use of instances becomes inconsistent. This is indicated, in particular, by the difference in the values ​​of batteries, sometimes reaching 10% (with a sequential cyclic reference to instances a la “ round - robin, ” this simply cannot happen).
• If the Accumulator exceeds 500,000, the corresponding instance of RC 4 will be initialized twice — first with the first thread and then with the second — which will undoubtedly have an impact on performance.

The described error is not so critical as to fertilize the bald spot with ashes or  dig in the nearest cave in anticipation of the apocalypse. However, getting rid of it will not be superfluous at all, especially since it can be done with a light stroke of the pen:

or the same, but for art lovers:

You can learn more about deadlock functions in MSDN [9].

With a sword bald

The determinism inherent in the software (and in some cases hardware) implementation of any algorithm is the true Achilles heel of cryptographic systems. And sadly enough, it is the implementation errors that discredit the protected environment more often than the vulnerabilities found in mathematical models. The case is further complicated by the fact that developers sometimes deliberately refuse to use robust protection mechanisms, explaining this, for example, by the inability to ensure maximum speed combined with an acceptable level of security. Moreover, the “contract with conscience” clause is not limited to the clause on impaired productivity. With no less success, other “obstructive arguments” are also going on. Recall, at least, our Jan Liberman remote attack on MS SQL Server [10], which we would not be able to conduct, if security in the TDS protocol was sacrificed for the feature of backward compatibility with less protected clients. So traces of compromises can be found in almost any applied solution and the results of the UuidCreate study confirm this once again.

A cryptographically reliable pseudo-random number generator should not only produce a sequence that seems seemingly random at first glance, but also have two important properties - Backward and Forward Security .

Backward security - does not allow an attacker to predict the states in which he will be in the future according to the current state of the generator. In order to reduce the detrimental effect of determinism and to somehow meet this requirement, the algorithm usually provides for regular state updates ( rekey) a true random bit sequence. And the more often it is executed, the more resistant is the generator. Entropy sources can be indications of performance counters, measurements of thermal sensors, processor registers values ​​at a certain point in time, and other values ​​remaining secret to an intruder with seven seals (refer to the book by Michael Howard and David Leblank Protected Code [11] without regretting the paper, more than a hundred sources for CryptGenRandom were listed separated by commas ).

Now we already know what test the Uuid generator was made of and we can confidently say that it does not stand the test for backward security . A full status update occurs after 4 · 10 ⁶ bytes of output (8 copies of RC 4 * 500 000 bytes), so an attacker who managed to get the "cast" of all registers and S- blocks of UuidCreate at a certain point in time can predict up to 250,000 future Uuid -values . Moreover, the source of entropy of the generator is the PRNG Windows represented by SystemFunction  036, which, taking into account the predictability of the latter [8], increases the length of the compromised data stream to 256 · 10 ⁶ bytes!

Indeed, CryptGenRandom , like UuidCreate , consists of 8 RC 4 instances . Each of them goes through the re-initialization procedure when the output byte counter begins to exceed 16 KB. This is almost 30 times less than that of the Uuid- generator, but not enough to be considered reliable. Instances of RC 4 in CryptGenRandom are used evenly, therefore, a full update of the PRNG state is performed only after 128 KB of output (8 copies of RC 4 * 16 K b).

The rc 4_ safe _ key function consumes 256 bytes of the Windows PRNG output per one reinitialization of an instance in the Uuid generator , while 2 KB (8 instances * 256 bytes of the key) are spent on a full update. Using simple arithmetic operations, it is easy to calculate how many Uuid values ​​the attacker can predict if he can get the current state of CryptGenRandom : 

4 · 10 ⁶  * (128 Kb / 2 Kb)   = 256 · 10 ⁶ bytes;

256 · 10 ⁶ bytes / 16 bytes in one Uuid-value = 16 · 10 ⁶ Uuid- values

Fig.3 Hierarchy of sources of entropy

You will ask why it was necessary to use a surrogate derived from PRNG Windows instead of sources of entropy of the OS . I'll start from afar. First of all, no one in their right minds placed great hopes on the resilience of UuidCreate (and those who have laid are simply obliged to read this article to the end). Sami demiurges quite clearly outlined its position in RFC4122 [1]: «the Do not Assume That UUIDs are hard to matching guess; they should not be used as security capabilities, for example. A predictable random number source will exacerbate the situation » . So developers never had a goal to create a safe Uuid generator. Unfortunately, the planet Earth is still trampling on goblins (not only trampling, but also express payment cards are stamped!), Which apply to such warnings without proper trepidation.

Secondly, for unnecessary access to the system registry key, where the 80-byte Seed is stored , or calling the function of the KSecDD driver, you will have to pay with expensive CPU time ticks ( .NET- users cannot understand;) This will be especially noticeable in the latter case, since it requires switching to kernel mode (here's a compromise between performance and security). Third, creating a pseudo-random key for RC 4 with SystemFunction 036 is much easier than complicating your life with the overly complicated generator design.

We now turn to the second property of reliable PRNG - Forward Security . Its meaning is that the attacker who owns the current state of the generator should not extract any information about the previous output from it. In other words, PRNG should be designed as a unidirectional function, using hashing algorithms for this purpose.

But here, UuidCreate fails . The only transformations that we see in the code are limited to permutations within S -blocks. An attacker can easily perform these operations in the reverse order and obtain the preceding gamma of the generator:

So, suppose the attacker took a memory “cast” from the g_rc4SafeCtx structure and remembered the g_rc4TotalRequests access counter at time t such that T ₁ ≤ t ≤ T ₂ , where T ₁ is the time of the last complete generator update, and T ₂ is the time of the upcoming update . Then it can reproduce the generator output in the interval [ T ₁ ; t ) and predict the values ​​returned by the UuidCreate function until the occurrence of T ₂ .

There is, however, one nuance that must be taken into account. The value of the buffer I _i transmitted to UuidCreate during the i- th call is not always known to the attacker. And according to the scheme shown in Fig. 1, an XOR operation is performed between this value and the gamut of RC 4 . Therefore, at first glance, it seems that an attacker who does not know I _i will hardly be able to use the proposed attack model. However, in practice, the Uuid variable is either initialized with zeros, or it contains garbage that is on the stack by the time the memory is allocated. In the latter case, the probability of occurrence of correlations between different values ​​of I _i in the interval from T ₁ to T ₂ remains quite high, than the attacker will not fail to take advantage of (I will demonstrate this a little lower using the example of MS SQL Server ).

Now that you are familiar with the anatomy of UuidCreate and have mastered the theoretical part of the article, I would like to say a few words about the Uuid Big Brother console utility that I wrote to automate the attack procedure. The utility is able to take a dump of the state of the Uuid generator in any of the OS processes and to guess both the previous and subsequent Uuid values ​​(for a detailed description of the UBB parameters, see Appendix B).

Attack with the famous I _i

As a workout, I propose to hone our skill oracle on a simple guidgen application . exe , from time immemorial included in the delivery of Visual Studio [12]. This utility is notable because before calling UuidCreate, the buffer for the Uuid value is initialized with zeros (that is, I _i == NULL ). You can see this for yourself, since the guidgen source code is available for download to everyone [13]:

This is definitely a chance to exercise in foresight.

1. Run guidgen . exe and find it in the Task Manager ( the Task Manager ). Remember the process ID (for example, PID = 3912).
2. Remove the generator state dump with Uuid Big Brother and save it to the guidgen file . dmp :

The result of the command will be approximately as follows:

UBB hints to us that the process did not have time to initialize one or more RC4 instances, so part of the predicted Uuid values ​​will not be true.

1. Press the New Guid button 7 times in the GuidGen window (this will force the application to completely initialize the generator), then re-take the dump. The warning should disappear:

1. Now run ubb with the - g parameter (nothing prevents you from doing this on another machine, after copying the dump file there). The - g parameter causes the utility to predict all subsequent Uuid values.

1. Click the New Guid button again in the GuidGen window . The Result section displays the Uuid value (in the screenshot {1F00F7F3-8F0F-4473-80F2-D3B175CC93DB} ), which you managed to guess before the application generated it (in the 4th step in bold).

Pressing any key in UBB results in new values. By default, the utility issues them in portions of 8 elements each, but you can change this number using the key - o (for more details, see Appendix B).

Attack with unknown I _i

The time has come to recall Vasily Mudilov and figure out how he managed to circle the guys from the White Collars department around his finger. But first, make sure that the T - SQL NEWID () function actually uses the Windows UUID generator , and that the attack technique described here applies to scenarios with express payment cards. The listing shows the recovered code for MS SQL Server 2008 CTP 5 ( build 1075):

The next step is to figure out how to initialize buffer I _i before executing UuidCreate . To do this, we need SQL Internals Profiler - a tool developed by Jan Lieberman and indispensable in cases where you need to collect statistics on calls to internal functions of MS SQL Server . Now, in particular, we will be interested in the values ​​passed by the pguid pointer to the CoCreateGuid .  

Translated from Liberman, the phrase ' hpg 1; -' sounds like this: “The first parameter ( 1 ) of the function is a reference ( p ) to an archival value 16 bytes long ( h ) that needs to be intercepted before calling CoCreateGuid ( ; - ) . Group results by unique values ( g ) ". Those who wish to master this language can recommend an excellent Russian-Liberian phrasebook [14,15].

Let's see how NEWID behaves if you periodically contact it:

I got the following picture ( SQL Server 2008 CTP 5):